package xyz.sekai52799.answer.a201_a400;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Question241 {

//    给你一个由数字和运算符组成的字符串expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。
//
//    生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4 。
//
//
//
//    示例 1：
//
//    输入：expression = "2-1-1"
//    输出：[0,2]
//    解释：
//            ((2-1)-1) = 0
//            (2-(1-1)) = 2
//    示例 2：
//
//    输入：expression = "2*3-4*5"
//    输出：[-34,-14,-10,-10,10]
//    解释：
//            (2*(3-(4*5))) = -34
//            ((2*3)-(4*5)) = -14
//            ((2*(3-4))*5) = -10
//            (2*((3-4)*5)) = -10
//            (((2*3)-4)*5) = 10
//
//
//    提示：
//
//            1 <= expression.length <= 20
//    expression 由数字和算符 '+'、'-' 和 '*' 组成。
//    输入表达式中的所有整数值在范围 [0, 99]
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    private static Map<String, List<Integer>> map = new HashMap<>();
    // 记录已经计算出来的字符串对应的值，避免重复计算。
    public static List<Integer> diffWaysToCompute(String input) {
        if (map.containsKey(input)){
            return map.get(input);
        }
        List<Integer> list = new ArrayList<>();
        int len = input.length();
        for (int i = 0; i < len; i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {  // 出现运算符号，递归求解前半段和后半段。
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                // -1   =>  left:[[0]]  right:[[1]]

                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                list.add(l + r);
                                break;
                            case '-':
                                list.add(l - r);
                                break;
                            case '*':
                                list.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (list.size() == 0) list.add(Integer.valueOf(input));
        // 单独一个数字的情况 (可能出现多位数)
        map.put(input, list);
        return list;
    }

}
